package algorithm.heap;

/**
 * leetcode : https://leetcode.com/problems/kth-largest-element-in-an-array/description/
 * Difficulty : Medium
 *
 * TopK问题一样
 * 即[3,2,3,1,2,4,5,5,6] 的数列里 第4大的数是4
 *
 * 难点：
 * 需要注意的是，我们构建的堆只符合顶堆性质，并没有符合右子大于左子的性质。
 *
 * 1，构建顶堆时，可以在构建堆的同时节点上浮。
 * 2，在入堆时，比较的同时不要赋值，在确定要交换哪个以后最终赋值。
 * 2，在入堆时，除了要判断父节点和两个子节点大小外，还需要留意子节点两个的大小
 *      举个栗子：在小顶堆中 val > left_child, 那么临时指针就可以指为left_child
 *      但是如果left>right 那么left上浮以后，就会破坏小顶堆性质
 *      所以接下来才需要比较: if(heap[left] > heap[right]) {hole=right}
 *
 * 入堆
 * 循环不变式:  hold < heap.length
 * 终止条件： tmpIndex = hole (也就是说这一次没有找到交换节点,那么hole就是最小节点了)
 * 在终止以后，需要最终把 val 赋值 也就是: heap[hole]=val
 *
 * 优化，在构建堆的同时，就可以对节点上浮操作
 * 每次循环的 index=i 为要当前的空位置 hole=i,
 * 当前要插入的值 tmp = array[i],
 * 当前初始父节点位置 parIndex = (i-1)/2; //或者是 parIndex=(hole-1)/2 都一样的
 *
 * 由于hole节点是要上浮的，所以
 * 循环不变式: hole > 0 && heap[parIndex] > tmp
 *
 * @Author Antony
 * @Since 2018/7/5 17:54
 */
public class KthLargestElementInArray {

    public static void main(String[] args) {
        int[] arr_1 = new int[]{3,2,3,1,2,4,5,5,6};     // 要求答案为4
        int k = 4;

        System.out.println(findKthLargest(arr_1, k));
    }

    // (leetcode beats 99.93%)
    public static int findKthLargest(int[] array, int k) {
        int[] heap = createMinTopHeap(array,k);
        for(int i=k; i<array.length; i++){
            if(array[i] > heap[0]){
                minHeapDown(heap, array[i]);
            }
        }

        return heap[0];
    }

    // 校验没问题
    static int[] createMinTopHeap(int array[], int k){
        int[] heap = new int[k];
        int childIndex,tmp,parIndex;

        //在入堆的时候, 顺便可以对节点上浮
        for(int i=0; i<k; i++){
            childIndex = i;
            tmp = array[i];
            parIndex = (i-1)/2;
            while(childIndex > 0 && heap[parIndex] > tmp){
                heap[childIndex] = heap[parIndex];
                childIndex = parIndex;
                parIndex = (parIndex-1)/2;
            }
            heap[childIndex] = tmp;
        }
        return heap;
    }


    // 可正确执行通过的解法,但是每次找出都要交换节点, 还可以优化
    public static void minHeapDown(int[] heap, int value){
        heap[0] = value;
        int parent = 0;
        int lChild, rChild, minIndex, tmp;
        while(parent < heap.length){
            lChild = parent*2+1;
            rChild = parent*2+2;
            minIndex = parent;

            if(lChild < heap.length && heap[minIndex] > heap[lChild]){
                minIndex = lChild;
            }

            if(rChild < heap.length && heap[minIndex] > heap[rChild]){
                minIndex = rChild;
            }

            if(minIndex == parent){
                break;
            }else{
                tmp = heap[parent];
                heap[parent] = heap[minIndex];
                heap[minIndex] = tmp;
                parent = minIndex;
            }
        }
    }


    // 对上一个方法的优化 (然而事实上并没有优化多少，时间一样)
    // 通过一个临时变量 tmpVal 保存要比较的值
    // 先左后右，左边如果符合了的话，将左边值赋值给tmpVal，然后拍与右边比
    public static void minHeapDown_bak(int[] heap, int value){

        int parent = 0;
        int lChild, rChild, minIndex, tmpVal;
        while(parent < heap.length){
            lChild = parent*2+1;
            rChild = parent*2+2;
            minIndex = parent;
            tmpVal = value;

            // 由于是先比左边，所以左边如果符合条件，就赋值 tmpVal=heap[lChild]
            if(lChild < heap.length && tmpVal > heap[lChild]){
                minIndex = lChild;
                tmpVal = heap[lChild];
            }

            if(rChild < heap.length && tmpVal > heap[rChild]){
                minIndex = rChild;
            }

            if(minIndex == parent){
                break;
            }else{
                heap[parent] = heap[minIndex];
                parent = minIndex;
            }
        }
        heap[parent] = value;
    }
}
